package com.shujia.day04;

public class Demo01ArrayOperator {
    public static void main(String[] args) {
        /*
            TODO 定义数组的 冒泡排序  二分查找
         */
        int[] intAr = {3, 2, 1, 5, 6, 4, 2, 1, 8};
        bubbleSort(intAr);
        System.out.println(getArrStr(intAr));
        int index = binarySearch(intAr, 0);
        System.out.println("获取到下标："+index);

    }

    public static int[] bubbleSort(int[] intArr) {
        /*
            冒泡排序：
                对相邻两个数据进行比较，将较小的数据前置，较大的数据后置，之后再去拿下一个数据进行比较

              第一层 2,1,3,5,6,4,2,1,8
              第二层 2,1,3,5,6,4,2,1,8
                ① 3 v 2 => 2 3
                ① 3 v 1 => 1 3
         */
        for (int i = 0; i < intArr.length - 1; i++) {
            for (int j = 0; j < intArr.length - i - 1; j++) {
                if (intArr[j] > intArr[j + 1]) {
                    int tmp = intArr[j + 1];
                    intArr[j + 1] = intArr[j];
                    intArr[j] = tmp;
                }
            }
        }

        return intArr;
    }

    /*
        二分查找：
            给定一个具体的数据，通过二分的方式在int类型的数组中进行遍历数据，如果遍历到，那么返回其下标
            如果没有遍历到则返回 -1
            [1, 1, 2, 2, 3, 4, 5, 6, 8]
            对于二分查找必须要求其数组为有序数组
            ① 先确定 开始下标 和结束下标
            ② 通过开始下标和结束下标确定 中间mid下标 通过mid 获取对应下标的值
            ③ 通过下标值和目标值进行比较
                1.如果相同则返回mid下标,程序结束
                2.如果当mid 小于 目标值那么需要将 开始下标设置为 mid + 1 再进行一轮比较
                3.如果当mid 大于 目标值那么需要将 结束下标设置为 mid - 1 再进行一轮比较
            注意：mid = 开始下标 + 结束下标 / 2 取整

     */
    public static int binarySearch(int[] intArr, int search) {
        int startIndex = 0;
        int endIndex = intArr.length - 1;
        while (startIndex <= endIndex) {
            int mid = (startIndex + endIndex) / 2;
            if (intArr[mid] == search) {
                return mid;
            }else if (intArr[mid] < search){
                startIndex = mid + 1;
            }else {
                endIndex = mid - 1;
            }
        }
        return -1;
    }


    public static String getArrStr(int[] strArr) {
        String arrStr = "[";
        for (int i = 0; i < strArr.length; i++) {
            if (i != strArr.length - 1) {
                arrStr += strArr[i] + ", ";
            } else {
                arrStr += strArr[i];
            }
        }
        arrStr += "]";
        return arrStr;
    }
}
